package com.dxb.test.sort;

/**
 * 箱排序
 * 基本思想：
 * BinSort想法非常简单，首先创建数组A[MaxValue]；
 * 然后将每个数放到相应的位置上（例如17放在下标17的数组位置）；
 * 最后遍历数组，即为排序后的结果。
 */
public class BinSort extends BaseSort {
    public BinSort(int[] array) {
        super(array);
    }

    @Override
    public void sort() {
        //找最大
        int max = 0;
        for (int i = 0; i < length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
        }
        //把数字放入数组
        boolean[][] newArray = new boolean[max + 1][length];
        for (int i = 0; i < length; i++) {
            if (newArray[array[i]] == null) {
                newArray[array[i]] = new boolean[length];
            }
            for (int j = 0; j < length; j++) {
                if (!newArray[array[i]][j]) {
                    newArray[array[i]][j] = true;
                    break;
                }
            }
        }
        //找非空并放入原数组
        int index = 0;
        for (int i = 0; i < max + 1; i++) {
            if (newArray[i] == null) {
                continue;
            }
            for (int j = 0; j < length; j++) {
                if (newArray[i][j]) {
                    array[index++] = i;
                } else {
                    break;
                }
            }
        }
    }

    public static void main(String args[]) {
        int[] array = {99, 78, 26, 17, 82, 36, 9, 81, 22, 100, 30, 20, 17, 85};
        BaseSort qs = new BinSort(array);
        qs.run();
    }
}
